package problem02_04;

//面试题02.04 分割链表
//https://leetcode.cn/problems/partition-list-lcci/

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode cur = head, tmp = newHead, prev = newHead;
        while(tmp.next != null && tmp.next.val < x) {
            tmp = tmp.next;
        }
        cur = tmp.next;
        while(cur != null) {
            if(cur.val < x) {
                ListNode next = cur.next;
                cur.next = tmp.next;
                tmp.next = cur;
                prev.next = next;
                cur = next;
                tmp = tmp.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        return newHead.next;
    }
}